#include <iostream>
#include <unordered_map>
#include <vector>
struct ListNode {
  int key;
  int value;
  ListNode *next;
  ListNode *pre;

  ListNode() : key(0), value(0), next(nullptr), pre(nullptr) {}
  ListNode(int key_, int value_, ListNode *pre_, ListNode *next_)
      : key(key_), value(value_), next(next_), pre(pre_) {}
};

class LRU {
private:
  int size_{0};
  int capacity_{0};
  ListNode *tail_{nullptr};
  ListNode *head_{nullptr};
  std::unordered_map<int, ListNode *> hashTable_;

public:
  LRU(int capacity) : capacity_(capacity), size_(0) {
    tail_ = new ListNode;
    head_ = new ListNode;
    head_->next = tail_;
    tail_->pre = head_;
  };
  void put(int key, int value) {
    if (hashTable_.count(key)) {
      ListNode *result = hashTable_.at(key);

      if (result->value != value) {
        result->value = value;
      }

      update(result);
      return;
    }

    if (this->size_ < this->capacity_) {
      //容量未满，插入
      addTohead(key, value);
      this->size_++;
      return;
    }

    //删除最后一个结点，插入一个新的结点到头
    deleteTailNode();
    addTohead(key, value);
  }
  int get(int key) {
    if (hashTable_.count(key)) {
      ListNode *result = hashTable_.at(key);
      update(result);
      return result->value;
    }

    return -1;
  }

private:
  void update(ListNode *node) {
    node->pre->next = node->next;
    node->next->pre = node->pre;
    updateToHead(node);
  }

  void updateToHead(ListNode *node) {
    node->pre = head_;
    node->next = head_->next;
    head_->next = node;
  }

  void addTohead(int key, int value) {
    ListNode *node = new ListNode(key, value, nullptr, head_);
    node->pre = head_;
    node->next = head_->next;
    head_->next->pre = node;

    hashTable_.insert({key, node});
  };

  void deleteTailNode() {
    hashTable_.erase(tail_->pre->value);
    auto temp = tail_->pre;
    tail_->pre = temp->pre;
    temp->pre->next = tail_;

    delete temp;
  };
};

int main() {
  LRU lru(1);

  for (int i = 0; i < 1; i++) {
    lru.put(i, i + 3);
  }

  lru.put(1111, 90);
  for (int i = 0; i < 1; i++) {
    std::cout << lru.get(i) << std::endl;
  }

  return 0;
}